import com.sun.org.apache.xpath.internal.SourceTree;
import javafx.util.Pair;

import java.lang.reflect.Array;
import java.time.OffsetDateTime;
import java.util.*;
import java.util.logging.Level;
import java.util.stream.Collector;
import java.util.stream.Collectors;

/**
 * @author huangxin
 * @date 2020/7/16-19:23
 */
public class Test {


    /**
     * 一维数组的动态和
     *
     * @param nums
     * @return
     */
    public int[] runningSum(int[] nums) {
        int[] arr = new int[nums.length];

        arr[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            arr[i] = arr[i - 1] + nums[i];
        }

        return arr;
    }


    /**
     * 给你一个整数数组 nums 。
     * <p>
     * 如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
     * <p>
     * 返回好数对的数目。
     *
     * @param nums
     * @return
     */
    public static int numIdenticalPairs(int[] nums) {
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] == nums[j] && i < j) {
                    count++;
                }
            }
        }

        return count;
    }


    /**
     * 糖果最多的孩子
     *
     * @param candies
     * @param extraCandies
     * @return
     */
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        ArrayList<Boolean> list = new ArrayList<>();
        int max = candies[0];

        for (int candy : candies) {
            max = Math.max(max, candy);
        }


        for (int candy : candies) {
            list.add(candy + extraCandies >= max);
        }

        return list;
    }


    public String reformatDate(String date) {
        String[] arr = date.split(" ");

        HashMap<String, String> map = new HashMap<>();
        String[] month = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
        for (int i = 0; i < month.length; i++) {
            map.put(month[i], String.format("%02d", i + 1));
        }

        return arr[2] + "-" + map.get(arr[1]) + "-" + String.format("%02d", Integer.valueOf(arr[0].substring(0, arr[0].length() - 2)));
    }


    /**
     * 等差数列
     *
     * @param arr
     * @return
     */
    public boolean canMakeArithmeticProgression(int[] arr) {

        Arrays.sort(arr);

        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] - arr[i - 1] != arr[i + 1] - arr[i]) {
                return false;
            }
        }
        return true;

    }


    /**
     * @param path
     * @return
     */
    public boolean isPathCrossing(String path) {

        Set<Integer> set = new HashSet<>();

        int x = 0;
        int y = 0;
        set.add(getHash(x, y));
        for (char s : path.toCharArray()) {
            switch (s) {
                //北
                case 'N':
                    y += 1;
                    break;
                //南
                case 'S':
                    y -= 1;
                    break;
                //东
                case 'E':
                    x += 1;
                    break;
                //西
                case 'W':
                    x -= 1;
                    break;
                default:
                    break;
            }

            //通过hash获取x+y的哈希值
            //通过set.add方法判断是否重复
            if (!set.add(getHash(x, y))) {
                return true;
            }
        }

        return false;
    }

    public int getHash(int x, int y) {
        return x * 20001 + y;
    }


    public double average(int[] salary) {
        Arrays.sort(salary);
        int total = 0;
        for (int i = 1; i < salary.length - 1; i++) {
            total += salary[i];
        }

        return total / (salary.length - 2.0);
    }

    public int xorOperation(int n, int start) {
        int result = start;
        for (int i = 1; i < n; i++) {
            result ^= start + 2 * i;
        }
        return result;
    }


    public int[] shuffle(int[] nums, int n) {
        int[] result = new int[nums.length];
        for (int i = 0; i < n * 2; i += 2) {
            result[i] = nums[i / 2];
            result[i + 1] = nums[i / 2 + n];
        }
        return result;
    }

    public static int[] finalPrices(int... prices) {
        for (int i = 0; i < prices.length; i++) {
            int j = i + 1;
            while (j < prices.length) {
                if (prices[i] >= prices[j]) {
                    prices[i] -= prices[j];
                    break;
                }
                j++;
            }
        }

        return prices;
    }


    public int maxProduct(int[] nums) {
        Arrays.sort(nums);
        return Math.max((nums[nums.length - 1] - 1) * (nums[nums.length - 2] - 1), (nums[0] - 1) * (nums[1] - 1));
    }


    public boolean canBeEqual(int[] target, int[] arr) {
        Arrays.sort(target);
        Arrays.sort(arr);
        return Arrays.equals(target, arr);
    }

    public int isPrefixOfWord(String sentence, String searchWord) {
        String[] split = sentence.split(" ");
        for (int i = 0; i < split.length; i++) {
            if (split[i].startsWith(searchWord)) {
                return i + 1;
            }
        }
        return -1;
    }

    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int count = 0;
        for (int i = 0; i < startTime.length; i++) {
            if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
                count++;
            }
        }
        return count;
    }

    /**
     * 最长连续字串
     *
     * @param s
     * @return
     */
    public int maxPower(String s) {
        int max = 1;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; ) {
            int count = 1;
            int j = i + 1;
            while (j < chars.length && chars[i] == chars[j]) {
                count++;
                j++;
            }
            i = j;
            if (count > max) {
                max = count;
            }
        }
        return max;
    }


    public static List<String> buildArray(int n, int... target) {
        ArrayList<String> strings = new ArrayList<>();

        int j = 1;
        for (int i = 0; i < target.length; i++) {
            while (j < n && j != target[i]) {
                strings.add("Push");
                strings.add("Pop");
                j++;
            }
            strings.add("Push");
            j++;
        }
        return strings;
    }

    public String destCity(List<List<String>> paths) {
        Set<String> collect = paths.stream().map(item -> item.get(0)).collect(Collectors.toSet());
        for (List<String> path : paths) {
            if (!collect.contains(path.get(1))) {
                return path.get(1);
            }
        }
        return null;
    }

    public static int maxScore(String s) {
        int max = 0, con1 = 0, con0 = 0;
        for (int i = 0; i < s.length(); i++) {
            con1 += s.charAt(i) - '0';
        }
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '0') {
                con0++;
            } else {
                con1--;
            }
            max = Math.max(max, con0 + con1);
        }
        return max;
    }


    public static String reformat(String s) {
        ArrayList<Character> letters = new ArrayList<>();
        ArrayList<Character> nums = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if (c >= 48 && c <= 57) {
                nums.add(c);
            } else {
                letters.add(c);
            }
        }

        if (Math.abs(letters.size() - nums.size()) > 1) {
            return "";
        }

        StringBuilder result = new StringBuilder();
        if (letters.size() > nums.size()) {
            result.append(letters.get(0));
            for (int i = 1; i < letters.size(); i++) {
                result.append(nums.get(i - 1));
                result.append(letters.get(i));
            }

        } else if (nums.size() > letters.size()) {
            result.append(nums.get(0));
            for (int i = 1; i < nums.size(); i++) {
                result.append(letters.get(i - 1));
                result.append(nums.get(i));
            }
        } else {
            for (int i = 0; i < letters.size(); i++) {
                result.append(letters.get(i));
                result.append(nums.get(i));
            }
        }
        return result.toString();

    }


    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];

        for (int i = 0; i < nums.length; i++) {

            if (map.containsKey(nums[i])) {
                result[0] = i;
                result[1] = map.get(nums[i]);
                return result;
            }

            map.put(target - nums[i], i);
        }


//        for (int num : nums) {
//
//            for (int i : nums) {
//                if (num != i && target - num == i) {
//
//                }
//            }
//        }
//
//        for (int i = 0; i < nums.length; i++) {
//
//
//            for (int j = 0; j < nums.length; j++) {
//                if (i != j && target - nums[i] == nums[j]) {
//                    return new int[]{i, j};
//                }
//            }
//        }

        return null;
    }


    public int romanToInt(String s) {
        //IX VX
        //XL XC
        //CD CM

        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i + 1 < s.length() && getValue(s.charAt(i)) < getValue(s.charAt(i + 1))) {
                result += getValue(s.charAt(i + 1)) - getValue(s.charAt(i));
                i++;
            } else {
                result += getValue(s.charAt(i));
            }
        }

        return result;
    }

    public int getValue(char c) {
        switch (c) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }

    public int reverse(int x) {
        long n = 0;
        while (x != 0) {
            n = n * 10 + x % 10;
            x = x / 10;
        }
        return (int) n == n ? (int) n : 0;
    }


    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        return x == reverse(x);
    }

    public static boolean checkPossibility(int... nums) {
        if (nums.length < 3) {
            return true;
        }

        int count = 0;
        if (nums[0] > nums[1]) {
            nums[0] = nums[1];
            count++;
        }

        for (int i = 1; i < nums.length - 1; i++) {
            int right = nums[i + 1];
            if (nums[i] > right) {
                count++;


                if (count > 1) {
                    return false;
                }

                int left = nums[i - 1];

                if (left > right) {
                    nums[i + 1] = nums[i];
                } else {
                    nums[i] = left;
                }
            }
        }

        return true;
    }

    public static boolean buddyStrings(String a, String b) {
        if (a.length() != b.length() || "".equals(a)) {
            return false;
        }

        //重复字符
        if (a.equals(b)) {
            HashSet<String> set = new HashSet<>(Arrays.asList(a.split("")));
            return set.size() != a.length();
        }

        char[] charsA = a.toCharArray();
        char[] charsB = b.toCharArray();

        int[] arr = new int[2];
        arr[0] = -1;
        arr[1] = -1;

        int count = 0;
        for (int i = 0; i < charsA.length; i++) {
            if (charsA[i] != charsB[i]) {
                count++;
                if (count > 2) {
                    return false;
                }
                arr[count - 1] = i;
            }
        }

        if (count == 2) {
            return charsA[arr[0]] == charsB[arr[1]] && charsA[arr[1]] == charsB[arr[0]];
        }
        return false;
    }


    public int findNearest(int n, int[] heaters) {//找到离n最近的供暖器
        int ans = 1500000000;

        return ans;
    }

    public int findRadius(int[] houses, int[] heaters) {
        int rad = -1;
        for (int i = 0; i < houses.length; i++) {
            int ans = 1500000000;
            //供暖器取离得最近的那个的半径
            for (int j = 0; j < heaters.length; j++) {
                ans = Math.min(ans, Math.abs(heaters[j] - houses[i]));
            }

            //最小加热半径要取所有半径中最大的
            rad = Math.max(rad, ans);
        }
        return rad;
    }

    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (flowerbed.length == 1 && flowerbed[0] == 0 && n <= 1) {
            return true;
        }
        if (flowerbed.length == 2 && flowerbed[0] == 0 && flowerbed[1] == 0 && n <= 1) {
            return true;
        }

        int count = 0;

        for (int i = 0; i < flowerbed.length; ) {
            if (i == 0) {
                if (flowerbed[i] == 0 && flowerbed[i + 1] == 0) {
                    flowerbed[i] = 1;
                    count++;
                }
                i += 2;
            } else if (i == flowerbed.length - 1) {
                if (flowerbed[i] == 0 && flowerbed[i - 1] == 0) {
                    flowerbed[i] = 1;
                    count++;
                }
                i += 2;
            } else if (flowerbed[i] == 0 && flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                flowerbed[i] = 1;
                count++;
                i += 2;
            } else {
                i++;
            }
        }


        return count >= n;
    }


    public int lengthOfLastWord(String s) {
        String[] arr = s.split(" ");
        return arr.length > 0 ? arr[arr.length - 1].length() : 0;
    }


    public static boolean judgeSquareSum(int c) {
        int i = (int) Math.sqrt(c);
        int j = 0;
        while (j <= i) {

            int total = j * j + i * i;
            if (total > c) {
                i--;
            } else if (total < c) {
                j++;
            } else {
                return true;
            }
        }

        return false;
    }

    public static int repeatedStringMatch(String a, String b) {
        int len = a.length() * 2 + b.length();
        if (a.contains(b)) {
            return 1;
        }

        HashSet<String> aSet = new HashSet<>(Arrays.asList(a.split("")));
        HashSet<String> bSet = new HashSet<>(Arrays.asList(b.split("")));
        if (!aSet.containsAll(bSet)) {
            return -1;
        }

        StringBuilder tmp = new StringBuilder(a);

        for (int i = 0; i < len; i++) {
            tmp.append(a);
            if (tmp.toString().contains(b)) {
                //第一次叠加,i为0,相当于两遍,所以要+2
                return i + 2;
            }
        }
        return -1;
    }


    public static int countPrimes(int n) {
//
//        boolean[] isPrim = new boolean[n];
//        // 将数组都初始化为 true
//        Arrays.fill(isPrim, true);
//
//        for (int i = 2; i < n; i++) {
//            if (isPrim[i]) {
//                // i 的倍数不可能是素数了
//                for (int j = 2 * i; j < n; j += i) {
//                    isPrim[j] = false;
//                }
//            }
//        }
//
//        int count = 0;
//        for (int i = 2; i < n; i++) {
//            if (isPrim[i]) {
//                count++;
//            }
//        }
//
//        return count;

        if (n < 3) {
            return 0;
        }
        int[] arr = new int[n];


        for (int i = 2; i < n; i++) {
            for (int j = 2 * i; j < n; j += i) {
                if (arr[j] == 0) {
                    arr[j] = -1;
                }
            }
        }

        int count = 0;

        for (int i = 2; i < n; i++) {
            if (arr[i] == 0) {
                count++;
            }
        }


        return count;
    }


//    public int numMagicSquaresInside(int[][] grid) {
//        if (grid.length < 3 || grid[0].length < 3) {
//            return 0;
//        }
//
//        for (int i = 0; i < grid.length - 3; i++) {
//            for (int j = 0; j < grid[0].length; j++) {
//                /*
//                 0 1 2
//                 3 4 5
//                 6 7 8
//                 */
//
//
//            }
//        }
//
//
//    }


    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        double max = sum / (k * 1.0);

        for (int i = k; i < nums.length; i++) {
            sum = sum - nums[i - k] + nums[i];
            max = Math.max(max, sum / (k * 1.0));
        }

        return max;
    }


    public static int findPairs(int[] nums, int k) {
        if (k < 0) {
            return 0;
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }

        if (k == 0) {
            Map<Integer, List<Integer>> collect = list.stream().collect(Collectors.groupingBy(i -> i));
            return (int) collect.values().stream().filter(i -> i.size() > 1).count();
        }

        Collections.sort(list);
        HashSet<Integer> set = new HashSet<>(list);

        int count = 0;
        for (Integer integer : set) {
            if (set.contains(integer + k)) {
                count++;
            }
        }

        return count;
    }

    public static String licenseKeyFormatting(String s, int k) {
        StringBuilder stringBuilder = new StringBuilder(s.replaceAll("-", "").toUpperCase());
        if (k < 1) {
            return stringBuilder.toString();
        }
        for (int i = stringBuilder.length() - k; i > 0; i -= k) {
            stringBuilder.insert(i, '-');
        }

        return stringBuilder.toString();
    }

    public static int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }

        if (haystack.length() < needle.length()) {
            return -1;
        }

        if (haystack.length() == needle.length()) {
            return haystack.equals(needle) ? 0 : -1;
        }

        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            for (int j = 0; j < needle.length(); j++) {
                if (needle.charAt(j) != haystack.charAt(i + j)) {
                    break;
                }

                if (j == needle.length() - 1) {
                    return i;
                }
            }
        }


        return -1;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            } else {
                map.put(nums[i], i);
            }
        }
        return false;

    }

    public int trailingZeroes(int n) {
        int count = 0;
        while (n >= 5) {
            count += n / 5;
            n = n / 5;
        }

        return count;

    }


    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) {
            return false;
        }

        return subFrom(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public boolean subFrom(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }

        if (s == null || t == null) {
            return false;
        }

        if (s.val != t.val) {
            return false;
        }

        return subFrom(s.left, t.left) && subFrom(s.right, s.right);
    }


    /**
     * 转成3进制,计算1后面是否全部为0
     *
     * @param n
     * @return
     */
    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("10*$");
    }


    public String longestWord(String[] words) {

        if (words.length == 0) {
            return "";
        }

        //排序
        Arrays.sort(words);

        HashSet<String> set = new HashSet<>();

        String result = "";


        for (String word : words) {
            //长度为1则为第一个,其余要判断set中是否存在word去掉最后一位后的字符串
            if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
                result = word.length() > result.length() ? word : result;
                set.add(word);
            }
        }

        return result;
    }


    public int numPrimeArrangements(int n) {
        int[] zhishu = {
                2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
                83, 89, 97
        };
        //计算质数个数
        int nzhishu = 0;
        for (int c : zhishu) {
            if (n >= c) {
                nzhishu++;
            }
        }
        //计算非质数的个数
        int nfeizhishu = n - nzhishu;
        long ans = 1;
        for (int i = nfeizhishu; i > 1; i--) {
            if (ans < 1000000007 / i) {
                ans *= i;
            } else {
                ans = ans * i % 1000000007;
            }
        }
        for (int i = nzhishu; i > 1; i--) {
            if (ans < 1000000007 / i) {
                ans *= i;
            } else {
                ans = ans * i % 1000000007;
            }
        }
        return (int) ans % 1000000007;
    }

    public boolean isIsomorphic(String s, String t) {
        if (s.isEmpty() && t.isEmpty()) {
            return true;
        }
        if (s.isEmpty() || t.isEmpty() || s.length() != t.length()) {
            return false;
        }


        HashMap<Character, Character> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) {
                if (map.containsValue(t.charAt(i))) {
                    return false;
                }
                map.put(s.charAt(i), t.charAt(i));
            } else {
                if (map.get(s.charAt(i)) != t.charAt(i)) {
                    return false;
                }
            }

        }

        return true;
    }

    public List<List<Integer>> largeGroupPositions(String string) {
        ArrayList<List<Integer>> list = new ArrayList<>();

        int index = 0;
        while (index < string.length() - 1) {
            int pre = -1;
            int count = 0;
            while (index + 1 < string.length() && string.charAt(index) == string.charAt(index + 1)) {
                if (pre == -1) {
                    pre = index;
                }
                count++;
                index++;
            }

            if (pre != -1 && count >= 2) {
                ArrayList<Integer> arr = new ArrayList<>();
                arr.add(pre);
                arr.add(index);
                list.add(arr);
            }
            index++;
        }


        return list;
    }

    public boolean repeatedSubstringPattern(String s) {
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.length() % (i + 1) == 0) {
                StringBuilder stringBuilder = new StringBuilder();
                String substring = s.substring(0, i + 1);
                for (int j = 0; j < s.length() / (i + 1); j++) {
                    stringBuilder.append(substring);
                }
                if (stringBuilder.toString().equals(s)) {
                    return true;
                }
            }
        }
        return false;
    }


    public int findLHS(int... nums) {


        Arrays.sort(nums);

        if (nums.length == 0 || nums[0] == nums[nums.length - 1]) {
            return 0;
        }

        int max = 0;
        int i = 0;

        while (i < nums.length - 1) {
            int j = i;
            int pre = -1;
            while (j + 1 < nums.length && nums[j + 1] - nums[i] < 2) {

                j++;
                if (pre == -1 && nums[j] - nums[i] > 0) {
                    pre = j;
                }
            }


            if (nums[j] - nums[i] > 0) {
                max = Math.max(j - i + 1, max);
            }

            if (pre != -1) {
                i = pre;
            } else {
                i++;
            }
        }
        return max;
    }

    public String getHint(String secret, String guess) {
        int[] nums = new int[10];
        int countA = 0, countB = 0;
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                countA++;
            } else {
                if (nums[guess.charAt(i) - '0']-- > 0) {
                    countB++;
                }
                if (nums[secret.charAt(i) - '0']++ < 0) {
                    countB++;
                }
            }
        }
        return countA + "A" + countB + "B";
    }


    public void merge(int[] nums1, int m, int[] nums2, int n) {
//        int i = m + n - 1;
//        m--;
//        n--;
//
//        while (n >= 0) {
//            if (m >= 0 && nums1[m] > nums2[n]) {
//                nums1[i] = nums1[m];
//                m--;
//            } else {
//                nums1[i] = nums2[n];
//                n--;
//            }
//            i--;
//        }
        int i = m + n - 1;
        m--;
        n--;
        while (n >= 0) {
            if (m >= 0 && nums1[m] > nums2[n]) {
                nums1[i] = nums1[m];
                m--;
            } else {
                nums1[i] = nums2[n];
                n--;
            }
            i--;
        }
    }

    public boolean hasCycle(ListNode head) {

        if (head == null) {
            return false;
        }


        ListNode slow = head;

        ListNode fast = head.next;

        while (fast != null) {
            if (slow == fast) {
                return true;
            }

            slow = slow.next;

            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }

        return false;
    }


    public boolean checkStraightLine(int[][] c) {


        for (int i = 2; i < c.length; i++) {
            if ((c[1][1] - c[0][1]) * (c[i][0] - c[0][0]) != (c[i][1] - c[0][1]) * (c[1][0] - c[0][0])) {
                return false;
            }
        }

        return true;

    }


    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }

        StringBuilder str = new StringBuilder();

        while (num != 0) {

            if (num / 7 == 0) {
                str.insert(0, num % 7);
            } else {
                str.insert(0, Math.abs(num % 7));
            }

            num /= 7;

        }

        return str.toString();
    }

    public String makeGood(String s) {

        StringBuilder str = new StringBuilder(s);
        while (true) {
            boolean flag = true;

            char[] chars = str.toString().toCharArray();

            for (int i = 0; i < chars.length - 1; i++) {
                if (Math.abs(chars[i] - chars[i + 1]) == 32) {
                    flag = false;
                    str.replace(i, i + 2, "");
                    break;
                }
            }

            if (flag) {
                break;
            }
        }

        return str.toString();
    }

    public int dominantIndex(int... nums) {
        int max = 0, idx = 0, less = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                less = max;
                max = nums[i];
                idx = i;
            } else if (nums[i] > less) {
                less = nums[i];
            }
        }
        return max >= (less * 2) ? idx : -1;
    }


    public String toHex(int num) {
        char[] hex = "0123456789abcdef".toCharArray();
        StringBuilder str = new StringBuilder();
        while (num != 0) {
            int end = num & 15;//比较二进制的差异
            //// System.out.println(end);
            str.append(hex[end]);
            //无符号右移4位
            num >>>= 4;
        }
        if (str.length() == 0) {
            str.append("0");
        }
        //反转字符
        StringBuilder str0 = str.reverse();

        return str0.toString();

    }


    public boolean backspaceCompare(String s, String t) {

        return getStr(s).equals(getStr(t));
    }

    public String getStr(String s) {
        StringBuilder str = new StringBuilder(s);
        int index = 0;
        while (index < str.length()) {
            if (str.charAt(index) == '#') {
                str.delete(Math.max(index - 1, 0), index + 1);

                if (index > 0) {
                    index--;
                }
            } else {
                index++;
            }
        }
        return str.toString();
    }


    public boolean rotateString(String a, String b) {

        return a.length() == b.length() && (a + a).contains(b);
    }

    public static void main(String[] args) {
        System.out.println(new Test().backspaceCompare("ab##", "a#c#"));
    }
}


